package demo02;
/*课堂练习9：插入排序的缺点？
 * 时间复杂度高
 * 不是一个稳定的排序算法
 * 比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候
课堂练习10：希尔排序代替.（文字描述，代码演示（注释））
	希尔排序法的思路是将待排序的序列按照增量递减的方式分成若干个组，将原来较大的序列不断
切割成一个个小的子序列，使子序列符合“数目少且基本有序”这一条件，然后分别对各个子序列
进行直接插入排序，经过上述的操作后，使得整个序列已经基本有序，然后对整个序列进行一次
直接插入排序，即可得到一个整体有序的序列，排序完成！
*/
public class HomeWork09 {

    public static void main(String[] args) {
        int []a={8,4,10,23,6,9,3};
        System.out.print("原来序列如下：");
        for (int i = 0; i <a.length ; i++) {
            System.out.print(a[i]+" ");
        }
        sort(a);
        System.out.println();
        System.out.print("经过希尔排序后：");
        for (int i = 0; i <a.length ; i++) {
            System.out.print(a[i]+" ");
        }
    }
    private static  void sort(int arr[]) {
        int n=arr.length,d = n;
        while (d>1) {
            //每次对增量d进行折半
            d/=2;
            //单趟排序
            for (int i = 0; i < n - d; i++) {
                int right = i;
                int temp = arr[right + d];//存储待排序元素
                while (right >= 0) {
                    if (temp < arr[right]) {
                        //组内排序
                        arr[right + d] = arr[right];
                        //组内的下一元素，从右往左
                        right -= d;
                    }
                    else {
                        break;
                    }
                }
                //如果组内某一对元素已经有序则无需交换，将存储的待排序元素重新赋给原值
                arr[right + d] = temp;
            }
        }
    }
}